1. Field of the Invention:
The present invention relates to wireless personal area networks and wireless local area networks. More particularly, the present invention relates to systems, methods, devices, and computer program products for sharing bandwidth among multiple users in a wireless personal area network or wireless local area network environment.
2. Discussion of the Background:
The International Standards Organization's (ISO) Open Systems Interconnection (OSI) standard provides a seven-layered hierarchy between an end user and a physical device through which different systems can communicate. Each layer is responsible for different tasks, and the OSI standard specifies the interaction between layers, as well as between devices complying with the standard. One of the layers of the OSI model is the data link layer. The data link layer is responsible for placing data into frames that can be communicated at the physical layer of the model and for receiving acknowledgement frames. The data link layer is responsible for error checking as well as retransmission of frames that are not received and acknowledged. The data link layer includes two sublayers, a logical link control sublayer, and a media access control (MAC) sublayer.
In a wireless personal area network (WPAN) or a wireless local area network (WLAN) multiple devices communicate with one another while sharing the bandwidth allocated to the network. Because multiple devices are sharing the same bandwidth, it is necessary to coordinate the use of that bandwidth. A MAC protocol defines how that bandwidth is to be shared among the devices of the WPAN or WLAN.
One MAC protocol proposed for WPANs has taken the form of a slot cycle time division multiple access (TDMA) scheme. In a slot cycle TDMA scheme, each device transmits data in an allocated time slot per cycle. The amount of data that can be transmitted within that time slot is based on a variable slot size managed by a coordinator of the WPAN. In such slot cycle TDMA schemes, the coordinator determines the size of the slot to allocate to a particular user based on the frame size of the data that the user is using.
FIG. 1 illustrates an approach for planning bandwidth allocation in a slot cycle TDMA system. As shown in FIG. 1, a two-dimensional matrix 101 is populated for planning the sharing of the bandwidth by the devices in the network. The two-dimensional matrix represents time on one axis and the usage of bandwidth on the other axis. The partially populated matrix shown in FIG. 1 illustrates that user 1 requires ⅓ of the available bandwidth. Users 2 and 3, on the other hand, each require ⅙ of the available bandwidth. Users 4, 5, 6, and 7, each require 1/12 of the available bandwidth. On the right hand side of FIG. 1, is a fully populated matrix 102 showing two complete cycles 103, 104 for sharing the available bandwidth among seven users. Each row of the matrix represents one frame, and each four frames represent one cycle. It is clear from the fully populated matrix that user 1 is occupying ⅓ of the available bandwidth whereas users 2 and 3 are each occupying ⅙ of the available bandwidth, and users 4, 5, 6, and 7 are each occupying 1/12 of the available bandwidth.
FIG. 2 shows a more a detailed view of a frame in a slot cycle TDMA scheme such as that described in regard to FIG. 1. As shown in FIG. 2, a beacon 201 and a contention access period 202 is transmitted prior to the data fields of a first frame. The period of time between beacons 201 is fixed, and there may be multiple frames transmitted between subsequent beacons 201. A superframe includes not only the beacon 201 and the contention access period 202, but each of the frames sent after that beacon 201 and before a subsequent beacon 201 is sent. The frame shown in FIG. 2 corresponds to the first frame of cycle one 103 shown in FIG. 1. Accordingly, information from users 1, 2, and 4 are transmitted in this frame, which corresponds to the top row of the matrix 102 shown in FIG. 1. Prior to each user's transmission, a request to send (RTS) is transmitted by the user and a clear to send (CTS) is sent by the coordinator to the user telling the user that it is ok to transmit their data. As shown in the frame of FIG. 2, each portion of the frame corresponding to user data 204 is preceded by an RTS/CTS pair 203.
The beacon 201 is used by the controller to maintain synchronization with the users communicating with that controller. The contention access period 202 is the period in which all control messages between the controller and the users are transmitted, for example, it is in this period of time that a user would request to attach to the group sharing the bandwidth being controlled by the particular controller.
FIG. 3 illustrates exemplary frames for carrying out the bandwidth allocation shown in FIG. 1. As shown in FIG. 3, the frames can be grouped into two groups corresponding to superframe one 301, and superframe two 302. Each of the superframes includes a beacon and a contention access period, followed by successive groups of RTS/CTS pairs and their associated user data. Frames 1 and 3 of superframe two 302 illustrate the concept of a mini slot 303. A mini slot occurs when a user does not use the time slot reserved for them. For example, in frame 1 of superframe two 302 the time slot after user 1 was reserved for user 2 (as indicated in the second cell of the first row of the matrix 102 corresponding to cycle two 104 shown in FIG. 1). Similarly, the mini slot 303 in frame 3 of superframe two 302 corresponds to the time slot reserved for user 6 (as shown by the third cell of the third row of the matrix 102 corresponding to cycle two 104 in FIG. 1).
A slot cycle TDMA scheme requires that each node connected to a coordinator listen to the beacon 201 in order to receive coordination information pertaining to the present superframe. However, each node must continue to listen throughout the superframe so as to monitor the channel for the presence of RTS/CTS pairs corresponding to each particular node's time slot. Each node must keep track as the connected nodes use each time slot. For example, if a particular node has been assigned a time slot beginning at a set time, that user must track RTS/CTS pairs corresponding to those users occupying time slots before that user. This must be done so that users can adjust their assigned slot start time to account for users who have not used their allocated time slot. For example, as shown in FIG. 3, user 2 did not use its assigned time slot in the first frame of superframe two 302, as indicated by the presence of a mini slot 303. In this situation, user 4 must be listening so as to detect the absence of a CTS, which would have been sent by the controller to user 2 in response to an RTS request sent to the controller by user 2. In the examples shown in FIG. 3, user 2 never requested to use its time slot, and therefore, the mini slot (silent period) must be detected by user 4, so that user 4 can move up its scheduled start time so that the time allocated to user 2 that is not being used is not wasted. Once user 4 detects a mini slot, user 4 can send an RTS to the controller requesting permission to begin its transmission. The controller will send the CTS to user 4 authorizing user 4 to begin its transmission since the controller is aware that user 2 has forfeited their time slot. Accordingly, inherent with a slot cycle TDMA scheme, is the need for each user to listen to the controller at all times, not only in order to receive the initial slot assignment, but also to track the use of the allocated slots by each connected user. Furthermore, each user must transmit an RTS to the controller prior to each transmission.
The requirement to listen to the controller at all times, and to transmit an RTS to the controller prior to each transmission impacts the power consumption of each of the individual users. Moreover, since each user must track the use of each frame, the result is that the coordination of a time frame is not handled entirely by the coordinator, but rather, is a distributed function shared by not only the coordinator, but also each user connected to the coordinator. A slot cycle TDMA scheme also requires that the coordinator listen at all times so that corresponding CTS messages may be sent in response to each of the RTS messages received by the individual users.
FIG. 4 illustrates another disadvantage to slot cycle TDMA systems. Because the allocated slots are of a variable length, it is possible to have a situation where one user dominates the available bandwidth. Slot durations in slot cycle TDMA systems are determined based on the packet sizes of the data being transmitted by the users of the network. As shown in the example of FIG. 4, user 1 requires a slot in each frame of the superframe. However, if user 1 is transmitting large packets of data, it cannot be said that providing user 1 with ⅓ of the slots is synonymous with allocating user 1 with ⅓ of the bandwidth. Depending on the size of the slots, it is quite possible that a situation of slot cycle “unfairness” will exist, wherein one user is dominating the available bandwidth to a degree not proportional to the number of slots allocated to that user.
FIG. 5 illustrates a polling scheme for sharing bandwidth among several users. As shown in FIG. 5, rather than exchanging an RTS/CTS between the individual users and the coordinator, the coordinator polls the individual users prior to each allocated slot. Polling schemes suffer similar disadvantages to those described above in the context of the slot cycle TDMA scheme, such as, for example, the need to listen to the coordinator at all times.